<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>Document</title>
</head>
<body>
    <script>
        function Stack(){
            var items = []; //存储数据

            //从栈顶添加元素，也叫压栈
            this.push=function(item){
                items.push(item);
            };

            //从栈顶移除元素
            this.pop=function(){
                return items.pop();
            }

            //返回栈顶元素
            this.top=function(){
                return items[items.length-1];
            }

            //判断栈是否为空
            this.isEmpty=function(){
                return items.length == 0;
            }

            //返回栈的长度
            this.size=function(){
                return items.length;
            }

            //清空栈
            this.clear=function(){
                items=[];
            }
        }

        //判断括号是否合法函数
        function is_leagl_brackets(string){
            var stack=new Stack();
            if(string){
                for(var i=0; i<string.length; i++){
                    var item = string[i];
                    //遇到左括号入栈
                    if(item == "("){
                        stack.push(item);
                    }else if(item == ")"){
                        //遇到右括号判断是否为空 为空返回false 不为空删除栈顶元素
                        if(stack.isEmpty()){
                            return false;
                        }else{
                            stack.pop();
                        }
                    }
                }
            }
            //最后返回栈是否为空
            return stack.isEmpty();
        };
        console.log(is_leagl_brackets("()((((s))))")) //true
        console.log(is_leagl_brackets("()((((s)))))")) //false
        console.log(is_leagl_brackets("(())((((s)))))")) //false
        console.log(is_leagl_brackets(")()(")) //false

        //计算后缀表达式
        function calc_exp(exp){
            var stack = new Stack();
            for(var i=0;i<exp.length;i++){
                var item=exp[i];
                if(["+","-","*","/"].indexOf(item) !=-1){
                    var val1=stack.pop();
                    var val2=stack.pop();
                    var exp_str=val2 + item + val1;
                    //计算并解析字符串
                    var res=parseFloat(eval(exp_str));
                    //结果压入栈中
                    stack.push(res.toString());
                }else{
                    stack.push(item);
                }
            }
            //返回栈顶元素
            return stack.pop();
        }
        console.log(calc_exp(["4","13","5","/","+"]));

        //找出栈中最小值的方法且时间复杂度为O(1)
        function MinStack(){
            var data_stack=new Stack(); //存储数据
            var min_stack=new Stack();  //存储最小的值
            this.push=function(item){
                data_stack.push(item);
                //判断是否为空或者是否小于最小栈顶
                if(min_stack.isEmpty() || item < min_stack.top()){
                    min_stack.push(item);
                }else{
                    min_stack.push(min_stack.top());
                }
            }
            //弹出栈顶元素
            this.pop=function(){
                min_stack.pop();
                return data_stack.pop();
            }
            //返回栈的最小值
            this.min=function(){
                return min_stack.top();
            }
        }
        var minStack=new MinStack();
        minStack.push(2);
        minStack.push(1);
        minStack.push(23);
        console.log(minStack.min()) //1
        minStack.pop();
        minStack.pop();
        console.log(minStack.min()) //2



        //中缀表达式转后缀表达式
        var priority_map = {"+": 1,"-": 1,"*": 2,"/": 2};

        function infix_exp_2_postfix_exp(exp){
            var stack = new Stack();

            var postfix_lst = [];
            for(var i = 0;i<exp.length;i++){
                var item = exp[i];
                // 如果是数字,直接放入到postfix_lst中
                if(!isNaN(item)){
                    postfix_lst.push(item);
                }else if (item == "("){
                    // 遇到左括号入栈
                    stack.push(item);
                }else if (item == ")"){
                    // 遇到右括号,把栈顶元素弹出,直到遇到左括号
                    while(stack.top() != "("){
                        postfix_lst.push(stack.pop());
                    }
                    stack.pop();   // 左括号出栈
                }else{
                    // 遇到运算符,把栈顶的运算符弹出,直到栈顶的运算符优先级小于当前运算符
                    while(!stack.isEmpty() && ["+", "-", "*", "/"].indexOf(stack.top()) >= 0
                    && priority_map[stack.top()] >= priority_map[item]){
                        // 把弹出的运算符加入到postfix_lst
                        postfix_lst.push(stack.pop());
                    }
                    // 当前的运算符入栈
                    stack.push(item);
                }

            }

            // for循环结束后, 栈里可能还有元素,都弹出放入到postfix_lst中
            while(!stack.isEmpty()) {
                postfix_lst.push(stack.pop())
            }

            return postfix_lst
        };


        // 12+3
        console.log(infix_exp_2_postfix_exp(["12","+", "3"]))
        // 2-3+2
        console.log(infix_exp_2_postfix_exp(["2","-", "3", "+", "2"]))
        // (1+(4+5+3)-3)+(9+8)
        var exp = ["(","1","+","(","4","+","5","+","3",")","-","3",")","+","(","9","+","8",")"];
        console.log(infix_exp_2_postfix_exp(exp))

        // (1+(4+5+3)/4-3)+(6+8)*3
        var exp = ['(', '1', '+', '(', '4', '+', '5', '+', '3', ')', '/', '4', '-', '3', ')', '+', '(', '6', '+', '8', ')', '*', '3']
        console.log(infix_exp_2_postfix_exp(exp))

        console.log(infix_exp_2_postfix_exp(["12","+", "3","*", "5"]))
        console.log(infix_exp_2_postfix_exp(["12","*", "3","+", "5"]))
        console.log(infix_exp_2_postfix_exp(["(","1","+","2",")","*", "(","1","+","6",")"]))


        console.log(infix_exp_2_postfix_exp(["1","+","(","12","+", "3","*", "5",")"]))
    </script>
</body>
</html>